public class Solution3 {

    int[] w;
    int[] sum;
    int target;
    public Solution3(int[] w) {
        this.w = w;
        sum = new int[w.length];
        int temp = 0;
        for (int i = 0; i < w.length; i++) {
            temp += w[i];
            sum[i] = temp;
        }

        target = sum[sum.length - 1];
    }

    public int pickIndex() {
        if (sum.length == 1) return 0;
        int temp = (int) (Math.random() * target) + 1;
        int l = 0;
        int r = sum.length - 1;
        while (l < r) {
            int mid = (r + l) / 2;
            if (sum[mid] < temp) {
                l = mid + 1;
            } else r = mid;
        }
        return l;
    }
}
